# layer.mod    
# Yu Liu, 01/2006, add set FLOWSL for flows on the bottom layer
#
# by Yu Liu, 03/2001.   Based on arcflow.mod
# Arc-flow model for topology and working capacity allocation 
# considering all single NODE failures

# Declare the bottom layer topology with VERTS and EDGES
set VERTS;
set EDGES within {i1 in VERTS, VERTS diff {i1}};

# Flows on the bottom layer is FLOWSL where suffix 'L' for "Lower Layer"
set FLOWSL := {i1 in VERTS, VERTS diff {i1}};
# Each flow has a bandwidth requirement in parameter ML, default at 0 for bottom layer
param ML {FLOWSL} default 0 >=0; 

# matrix oBL has element 1 when the vertex is the original of the edge, 0 otherwise. 
param oBL {VERTS,EDGES} binary default 0;
# matrix dBL has element 1 when the vertex is the destination of the edge, 0 otherwise.
param dBL {VERTS,EDGES} binary default 0;

# matrix BL is the vertex to edge incidence matrix at bottem layer
# The element is 1 when the vertex is the original of the edge, 
#               -1 when the vertex is the destination of the edge,
#                0 otherwise.
param BL {VERTS,EDGES} integer default 0 >= -1 <= 1;

# matrices oDL, dDL, and DL are the flows to vertex incidence matrices at bottom layer
# They are similar to the declarition of oBL, dBL, and BL
param oDL {FLOWSL,VERTS} binary default 0;
param dDL {FLOWSL,VERTS} binary default 0;
param DL {FLOWSL,VERTS} integer default 0 >= -1 <= 1;


# Declare top layer topology
# node set is a subset of lower layer vertices, links are 
set NODES within VERTS;
set LINKS within {i1 in NODES, NODES diff {i1}};

# Declare flows on top layer
set FLOWS := {i1 in NODES, NODES diff {i1}};

# Each flow has a bandwidth requirement in parameter M
param M {FLOWS} default 1 >=0; 

param oB {NODES,LINKS} binary default 0;
param dB {NODES,LINKS} binary default 0;
param B {NODES,LINKS} integer default 0 >= -1 <= 1;
param oD {FLOWS,NODES} binary default 0;
param dD {FLOWS,NODES} binary default 0;
param D {FLOWS,NODES} integer default 0 >= -1 <= 1;

# matrix H maps each top layer LINK into a path on the bottom layer
var H {LINKS, EDGES} binary default 0;

# two auxilary matrices used for what? They are declasred as variables...
var T1 {LINKS} binary default 1;
var T2 {(i1,i2) in LINKS, NODES diff {i1,i2}} binary default 1;
#var A {FLOWS, LINKS} binary;
#var w {LINKS} integer default 0;

# total numbers of nodes and links on both layers
param MaxVert integer;
param MaxEdge integer;
param MaxNode integer ;
param MaxLink integer ;

# build a set of CUTS, 
# each of its elements hold a set of nodes.
# 
set POWNODES := 1 .. 2**MaxNode - 2; #get rid of 0 and 2^N -1, null cuts
set CUTS {k in POWNODES} := {i in NODES: (k div 2**(i-1)) mod 2 = 1};

# optimize the cost of top layer links on bottom layers, 
# assuming the unit link cost on the bottom layer
minimize topo_cost: 
  sum {(i1,i2) in LINKS, (j1,j2) in EDGES} H[i1,i2,j1,j2];

# Interlayer mapping matrix maps top layer links as the paths at bottom layer.
# These paths fulfill the flow conservation (mass balance) constraints
# The following formula assumes the first group of vertices (at bottom layer) are nodes (at top layer).
# the rest vertices are only for the bottom layer, so their net in/out flows are zeroes.
# H {B^l}^T = [ B^T | 0 ] 
s.t. mass_baH {(i1,i2) in LINKS, n1 in NODES}:
  sum {(j1,j2) in EDGES} BL[n1,j1,j2] * H[i1,i2,j1,j2]
      = B[n1,i1,i2];
s.t. mass_baH2 {(i1,i2) in LINKS, n1 in VERTS diff NODES}:
  sum {(j1,j2) in EDGES} BL[n1,j1,j2] * H[i1,i2,j1,j2]
      = 0;

# This formula assures the single failure of bottom layer will not partition the top layer.
# It is the matrix format of the 
# CH < Ce  or  C(e-H)>0
s.t. survH {(j1,j2) in EDGES, k in POWNODES}:
  sum{v1 in CUTS[k], v2 in NODES diff CUTS[k]:(v1,v2) in LINKS}
    (1- H[v1,v2,j1,j2]) >= 1; 

# added by Korn, H should have the same mapping for both directions
s.t. symH {(i1,i2) in LINKS, (j1,j2) in EDGES}:
	H[i2,i1,j2,j1] = H[i1,i2,j1,j2];

# problem to find interlayer mapping matrix H 
# that assures that the top layer is resilient to single link failure at the bottom layer
problem designH: topo_cost, mass_baH, mass_baH2, survH, symH,  H;

# Where those parameters are used? for what?  yliu:01/2006
param MaxFlow integer default 10;
param MaxHop integer default 60;

param t1 integer;
param t2 integer;
